'''
30 人 31 足比赛

不要让女生相邻
男生是可以任意排列的
'''
import copy

def solution(queue):
    if len(queue) == 30:
        return 1
    
    # 保存结果的变量
    result = 0

    # 队伍中还不够 30 个人
    # 1. 无条件添加一个男生
    copy1 = copy.deepcopy(queue)
    copy1.append(1)
    result = solution(copy1)

    # 2. 当队伍末尾是男生的时候，我们可以添加一个女生
    # queue 的最后一个元素是不是等于 1
    copy2 = copy.deepcopy(queue)
    if copy2[-1] == 1:
        copy2.append(0)
        result += solution(copy2)
    
    return result

print(solution([1]) + solution([0]))